import java.util.ArrayList;
import java.util.Arrays;

/**
 * @version Create on 2012-11-13
 * @author Yinzi Chen
 */

public class Triangle {

	public int minimumTotal(ArrayList<ArrayList<Integer>> triangle) {
		int n = triangle.size();
		if (n == 0)
			return 0;
		int[][] dp = new int[2][n];
		Arrays.fill(dp[0], Integer.MAX_VALUE);
		dp[0][0] = triangle.get(0).get(0);
		for (int i = 1; i < n; ++i) {
			Arrays.fill(dp[i % 2], Integer.MAX_VALUE);
			for (int j = 0; j <= i; ++j) {
				if (j - 1 >= 0)
					dp[i % 2][j] = Math.min(dp[i % 2][j],
							dp[(i + 1) % 2][j - 1] + triangle.get(i).get(j));
				if (j <= i - 1)
					dp[i % 2][j] = Math.min(dp[i % 2][j], dp[(i + 1) % 2][j]
							+ triangle.get(i).get(j));
			}
		}
		int res = Integer.MAX_VALUE;
		for (int i = 0; i < n; ++i)
			res = Math.min(dp[(n + 1) % 2][i], res);
		return res;
	}

	public static void main(String[] args) {

	}

}
